|
|
Regulated Parsing
Wolf, Dominik ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This work deals with advanced models of context-free grammars and explores the possibilities of adaptation and usefulness for deterministic parsing of non-context-free sructures by deep parsing method. It introduces adapted model of context-free grammar named LL programmed grammar and adapted deep pushdown automaton that makes deterministic parsing of non-context-free structures possible.
|
|
| |
|
|
Path-Controlled Grammars
Adamec, Ondřej ; Soukup, Ondřej (referee) ; Křivka, Zbyněk (advisor)
This thesis deals with path-controlled grammars, which are grammars that place restrictions on the paths in a derivation tree of a context-free grammar. The goal of this thesis is to create an algorithm for conversion between the path-controlled grammars and the state grammars, which is a di erent type of regulated grammars. Another goal is to study the generative power of path-controlled grammars based on the conversion algorithm. The conversion algorithm is implemented and tested on a number of path-controlled grammars. Also, its complexity is discussed. Finally, a parsing tool for path-controlled grammars is implemented. Complexity of this tool is analyzed as well.
|
|
|
Parsing Based on Regulated Grammars
Vaníček, Luboš ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
This thesis deals with regulated grammars. It describes their behavior and it compares them using different examples of context-sensitive languages. The thesis focuses mostly on programmed grammars. It modifies the methods of parsing and it uses them for programmed grammars. This thesis applies the developed method of parsing on context-sensitive languages and examines their power.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (referee) ; Doc. In.g Petr Sosík, Dr. (referee) ; Meduna, Alexandr (advisor)
Tato disertační práce zavádí jednostranné gramatiky s nahodilým kontextem jako řízené gramatiky založené na bezkontextových gramatikách. V těchto gramatikách je ke každému pravidlu přiřazena množina povolujících symbolů a množina zakazujících symbolů a množina pravidel je rozdělena na množinu levých pravidel s nahodilým kontextem a množinu pravých pravidel s nahodilým kontextem . Levým pravidlem s nahodilým kontextem lze přepsat neterminál pokud se všechny povolující symboly vyskytují vlevo od přepisovaného neterminálu a žádný zakazující symbol tam přítomen není. Pravé pravidlo s nahodilým kontextem lze aplikovat analogicky, ale ona kontrola na přítomnost a nepřítomnost symbolů je provedena doprava od přepisovaného neterminálu. Práce je rozdělena na tři části. První část uvádí motivaci za zavedením jednostranných gramatik s nahodilým kontextem a umisťuje materiál pokrytý v této práci do vědeckého kontextu. Poté dává přehled základů teorie formálních jazyků a některých méně známých oblastí, jejichž znalost je nutná pro pochopení studovaného tématu. Druhá část tvoří jádro práce. Formálně definuje jednostranné gramatiky s nahodilým kontextem a studuje je z mnoha pohledů. Mezi studovaná témata patří generativní síla, vztah k jiným typům gramatik, redukce, normální formy, nejlevější derivace, zobecněné a LL verze těchto gramatiky. Třetí část této práce zakončuje diskusi několika poznámkami. Mezi ně patří poznámky týkající se aplikovatelnosti zavedených gramatik v praxi, bibliografie a otevřených problémů.
|
|
|
Parsing Based on State Grammars
Novotný, Miroslav ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis's main focus is parsing, based on state grammars. The goal is to create a program, that will be able to load the grammar from input file. Based on a loaded grammar, the program will create an LL table and parse an input file using this table. The next goal is to study properties of parsing, based on state grammars, while using a created program as a stand point. Part of the testing will also be grammar structures which are not context-free.
|
|
|
On Erasing Rules in Regulated Grammars
Zemek, Petr ; Koutný, Jiří (referee) ; Meduna, Alexandr (advisor)
This work discusses the effect of erasing rules to the generative power of regulated grammars, which is a big open problem in the theory of regulated rewriting. It studies the possibility of removal of erasing rules from regulated grammars by aggregation of current, up-to-date results concerning this elimination and by presentation of a new condition, called k-limited erasing, under which all erasing rules can be always removed from regularly controlled context-free grammars without affecting their generative power. This result partially solves the abovementioned problem. Moreover, a new algorithm for elimination of erasing rules from context-free grammars is presented. This algorithm does not require any predetermination of so called epsilon-nonterminals (in contrast to the standard algorithm used in textbooks). In the conclusion, a significance of these results concerning syntactical analysis is discussed.
|
|
|
Regulated Grammar Systems
Tomko, Martin ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
Práce poskytuje přehled základů teorie formálních jazyků, regulovaných gramatik a analýzy LL(1) jazyků. Je zde navržen a analyzován algoritmus pro analýzu programovaných gramatik, inspirován LL(1) analyzátorem. Třída jazyků přijímaná tímto algoritmem je striktní nadtřídou LL(1) jazyků, obsahující některé jazyky, které nejsou bezkontextové. Tato třída se však jeví být neporovnatelná s třídou bezkontextových jazyků.
|
|
|
Regulated Grammar Systems
Tomko, Martin ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
Práce poskytuje přehled základů teorie formálních jazyků, regulovaných gramatik a analýzy LL(1) jazyků. Je zde navržen a analyzován algoritmus pro analýzu programovaných gramatik, inspirován LL(1) analyzátorem. Třída jazyků přijímaná tímto algoritmem je striktní nadtřídou LL(1) jazyků, obsahující některé jazyky, které nejsou bezkontextové. Tato třída se však jeví být neporovnatelná s třídou bezkontextových jazyků.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (referee) ; Doc. In.g Petr Sosík, Dr. (referee) ; Meduna, Alexandr (advisor)
Tato disertační práce zavádí jednostranné gramatiky s nahodilým kontextem jako řízené gramatiky založené na bezkontextových gramatikách. V těchto gramatikách je ke každému pravidlu přiřazena množina povolujících symbolů a množina zakazujících symbolů a množina pravidel je rozdělena na množinu levých pravidel s nahodilým kontextem a množinu pravých pravidel s nahodilým kontextem . Levým pravidlem s nahodilým kontextem lze přepsat neterminál pokud se všechny povolující symboly vyskytují vlevo od přepisovaného neterminálu a žádný zakazující symbol tam přítomen není. Pravé pravidlo s nahodilým kontextem lze aplikovat analogicky, ale ona kontrola na přítomnost a nepřítomnost symbolů je provedena doprava od přepisovaného neterminálu. Práce je rozdělena na tři části. První část uvádí motivaci za zavedením jednostranných gramatik s nahodilým kontextem a umisťuje materiál pokrytý v této práci do vědeckého kontextu. Poté dává přehled základů teorie formálních jazyků a některých méně známých oblastí, jejichž znalost je nutná pro pochopení studovaného tématu. Druhá část tvoří jádro práce. Formálně definuje jednostranné gramatiky s nahodilým kontextem a studuje je z mnoha pohledů. Mezi studovaná témata patří generativní síla, vztah k jiným typům gramatik, redukce, normální formy, nejlevější derivace, zobecněné a LL verze těchto gramatiky. Třetí část této práce zakončuje diskusi několika poznámkami. Mezi ně patří poznámky týkající se aplikovatelnosti zavedených gramatik v praxi, bibliografie a otevřených problémů.
|
guest ::
